package com.bootcamp.s2_0922.ds.Exercise._0924_ex1;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;

/**
 * @program: myClassCode
 * @description:
 * @author: Keyu Li
 * @create: 2021-09-24 21:09
 **/

public class PolandTransfer {
    public static void main(String[] args) {
//        inputByScanner();
        String[] infixs;
        infixs = createInfix();
        int[][] numValue = assignRandValue(infixs);
        int expreNumber = infixs.length;
        double[] result = new double[expreNumber];
        String[] postfixs = new String[expreNumber];
        for (int i = 0; i < 6; i++) {
            try {
                postfixs[i] = postFixTran(infixs[i]);
            } catch (RuntimeException e) {
                e.printStackTrace();
                continue;
            }
            result[i] = calPostFix(postfixs[i], numValue[i]);
            printExpre(infixs[i], postfixs[i], numValue[i], result[i]);
        }

    }

    // 通过键盘输入中缀表达式并计算结果
    private static void inputByScanner() {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            // 录入一个数学表达式
            System.out.println("input a normal expression( -+*^ )( , end): ");
            String expr = scanner.nextLine();
            if ("end".equals(expr)) break;
            // 转换为 逆波兰式 Reversed Polland Transfer，即后缀表达式 Postfix expression
            // 如果表达式不合法，则抛出异常，并重新输入
//            String expr = "a*b+(c+d)*e";
            String postfix;
            try {
                postfix = postFixTran(expr);
            } catch (RuntimeException e) {
                e.printStackTrace();
                continue;
            }
            System.out.println("Postfix expression: " + postfix);
            // 对 后缀表达式进行求解运算。
//            double result = calPostFix(postfix);
//            System.out.println("result is: " + result);
        }
    }

    // 初始化传入 中缀表达式
    private static String[] createInfix() {
        Expression expression = new Expression(10);
        expression.add("(a+b)*(c-d)");
        expression.add("a*(b-(c+d))+e/f");
        expression.add("a*b+((c+d)*e/f^g-(h-i)*j)");
        expression.add("a-b*(c+d)/(((e-f)*(g+h))+i)*j");
        expression.add("a-((((a+b)/(c-d)-5)");  // 抛出异常，左括号多不匹配
        expression.add("(a-b)*(c+d))))+e");     // 抛出异常，右括号多

        return expression.settle();
    }

    // 将中缀表达式中的字母，赋值为 1-100 之间的随机数
    private static int[][] assignRandValue(String[] infixs) {
        int[][] numValue = new int[infixs.length][];
        for (int i = 0; i < infixs.length; i++) {
            Random random = new Random();
            int count = 0;
            numValue[i] = new int[infixs[i].length()];
            for (int j = 0; j < infixs[i].length(); j++) {
                if (isNumber(infixs[i].charAt(j)))
                    numValue[i][count++] = random.nextInt(100) + 1;
            }
        }
        return numValue;
    }

    // 打印中缀表达式，后缀表达式，复制后的中缀表达式，以及计算的结果
    private static void printExpre(String infix, String postfix, int[] numValue, double result) {
        System.out.println("infix expression:\t" + infix);
        System.out.println("postfix expression:\t" + postfix);
        System.out.print("infix number:\t");
        int count = 0;
        for (int i = 0; i < infix.length(); i++) {
            char oper = infix.charAt(i);
            if (isNumber(oper)) {
//                System.out.print(" " + numValue[count++] + " ");
                System.out.print(numValue[count++]);
                continue;
            }
            System.out.print(oper);
        }
        System.out.println();
        System.out.println("result is:\t\t" + result);
    }


    // 将中缀表达式转换为后缀表达式
    public static String postFixTran(String expr) {
        // store postfix expression
        StringBuffer postfix = new StringBuffer();
        // create a stack to store operator and operand
        Stack<Character> operators = new Stack<>();
        for (int i = 0; i < expr.length(); i++) {
            char oper = expr.charAt(i);
            if (isNumber(oper)) {
                postfix.append(oper);
                continue;
            }
            boolean stackManuFlag = false;
            while (!operators.isEmpty()) {
                int flag = compare(operators.peek(), oper);
                if (flag < 0) {
                    postfix.append(operators.pop());
                } else if (flag > 0) {
                    break;
                } else {
                    operators.pop();
                    stackManuFlag = true;
                    break;
                }
            }
            if (stackManuFlag)
                continue;
            if (oper == ')')
                throw new RuntimeException("error expression!");
            operators.push(oper);
        }
        while (!operators.isEmpty()) {
            char oper = operators.pop();
            if (oper == '(' || oper == ')')
                throw new RuntimeException("error expression!");
            postfix.append(oper);
        }
        return postfix.toString();
    }

    // 对转换后的后缀表达式求值。
    public static double calPostFix(String postfix, int[] numValue) {
        Stack<Double> operands = new Stack<>();
        int count = 0;
        for (int i = 0; i < postfix.length(); i++) {
            char oper = postfix.charAt(i);
            if (isNumber(oper)) {
                operands.push(((double) numValue[count++]));
            } else {
                double o2 = operands.pop();
                double o1 = operands.pop();
                double r = 0;
                switch (oper) {
                    case '^':
                        r = Math.pow(o1, o2);
                        break;
                    case '*':
                        r = o1 * o2;
                        break;
                    case '/':
                        r = o1 / o2;
                        break;
                    case '+':
                        r = o1 + o2;
                        break;
                    case '-':
                        r = o1 - o2;
                        break;
                }
                operands.push(r);
            }
        }
        double result = operands.pop();
        if (!operands.isEmpty()) throw new RuntimeException("postfix transfer error!");
        return result;
    }

    /**
     * opN > opS, return 1, push opN in;
     * opN <= opS, return -1, pop out opS and continue compare;
     * opS cannot be )
     * opS = (, return 1, push opN in;
     * opN = (, return 1, push opN in;
     * opN = ), opS = (, return 0;
     * opN = ), return -1, pop out opS and continue compare;
     */
    private static int compare(char opS, char opN) {
        if (opS == '(') {
            if (opN == ')') return 0;
            return 1;
        }
        if (opN == '(') return 1;
        if (opN == ')') return -1;
        // compare comparator other than parenthesis
        if (opN == opS) return -1;
        if (opN == '^') return 1;
        if (opN == '*' && opS != '^') return 1;
        if (opN == '/' && opS != '^') return 1;
        return -1;
    }

    private static boolean isNumber(char oper) {
        return (oper >= 'a' && oper <= 'z')
                || (oper >= 'A' && oper <= 'Z')
                || (oper >= '0' && oper <= '9');
    }
}

class Expression {
    public String[] expre;
    int size;

    public Expression(int capacity) {
        this.expre = new String[capacity];
        size = 0;
    }

    public void add(String exp) {
        expre[size++] = exp;
    }

    public String[] settle() {
        return Arrays.copyOf(expre, size);
    }
}